package com.tgy.programmer_code_interview_guide._02_linkedList;

import com.tgy.leetcode.ListNode;

import java.util.HashSet;

/**
 * @Author: tgy
 * @Date: 1/27/21 11:40 AM
 */
public class _11_删除无序链表中值重复的节点 {

    public static ListNode removeRepeatValue(ListNode root){

        ListNode dummyNode = new ListNode();
        ListNode tailNode = dummyNode;

        ListNode node = root;

        while (node != null) {

            if (!findEqualNode(dummyNode.next,tailNode,node.val)) {

                tailNode.next = node;
                tailNode = node;
            }
            node = node.next;
        }

        tailNode.next = null;

        return dummyNode.next;
    }

    public static boolean findEqualNode(ListNode head,ListNode end,int val) {


        if (head == null) {

            return false;
        }

        ListNode node = head;

        while (true) {

            if (node.val == val) {

                return true;
            }

            if (node == end) {
                break;
            }

            node = node.next;
        }

        return false;
    }

    public static ListNode removeRepeatValue01(ListNode root){

        HashSet<Integer> set = new HashSet();

        ListNode dummyNode = new ListNode();
        ListNode tailNode = dummyNode;

        ListNode node = root;

        while (node != null) {

            if (!set.contains(node.val)) {

                tailNode.next = node;
                tailNode = node;
                set.add(node.val);
            }
            node = node.next;
        }

        tailNode.next = null;

        return dummyNode.next;
    }

    public static void main(String[] args) {

        ListNode root = ListNode.general(new int[]{1, 2, 3, 3, 2,5, 6});

        ListNode removeRoot = removeRepeatValue(root);

        ListNode.printListNode(removeRoot);
    }
}
